// ========================================================
// FIRST 30 PRIME NUMBERS
//
// Finds and displays the first 30 prime numbers.
//
// A prime number is an integer greater than 1 that can
// only be divided evenly by 1 and itself.
//
// This program tests each candidate using possible divisors.
// Division is tested using repeated subtraction.
//
// THIS PROGRAM DEMONSTRATES:
//
//   1. Finding prime numbers.
//   2. Calling a function with JAL.
//   3. Returning from a function with JALR.
//   4. Passing arguments in registers.
//   5. Returning a true-or-false result in a register.
//   6. Nested loops.
//   7. Division testing using repeated subtraction.
//   8. Conditional execution using BEQ and BLT.
//   9. Unconditional jumps using JAL with x0.
//  10. Counting the number of results produced.
//
// REGISTER USE:
//
//   x1  = return address
//   x5  = number of primes found
//   x6  = current candidate
//   x7  = current divisor
//   x8  = subtraction remainder
//   x9  = constant value 2
//   x10 = IsPrime function argument
//   x12 = IsPrime result: 1 = prime, 0 = not prime
//   x20 = number of primes requested
//
// EXPECTED OUTPUT:
//
//   2
//   3
//   5
//   7
//   11
//   13
//   17
//   19
//   23
//   29
//   31
//   37
//   41
//   43
//   47
//   53
//   59
//   61
//   67
//   71
//   73
//   79
//   83
//   89
//   97
//   101
//   103
//   107
//   109
//   113
// ========================================================


// --------------------------------------------------------
// Main program
// --------------------------------------------------------

start:
        addi  x5, x0, 0             // No primes found yet
        addi  x6, x0, 2             // First candidate is 2
        addi  x20, x0, 30           // Find 30 prime numbers

        cout  << "First 30 prime numbers:" << endl


// Test the current candidate.

CandidateLoop:
        add   x10, x6, x0            // Pass candidate to function

        jal   x1, IsPrime            // Test whether candidate is prime

        beq   x12, x0, NextCandidate // Skip display if not prime


// A prime number was found.

        cout  << x6 << endl

        addi  x5, x5, 1              // Increase prime count

        beq   x5, x20, EndProgram    // Stop after finding 30 primes


// Advance to the next possible number.

NextCandidate:
        addi  x6, x6, 1              // Candidate++
        jal   x0, CandidateLoop


// ========================================================
// IsPrime function
//
// Input:
//
//   x10 = number to test
//
// Output:
//
//   x12 = 1 if the number is prime
//   x12 = 0 if the number is not prime
//
// Method:
//
//   Try every divisor beginning with 2.
//   Repeatedly subtract the divisor from the candidate.
//   If the remainder becomes zero, the candidate is
//   divisible and therefore is not prime.
// ========================================================

IsPrime:
        addi  x12, x0, 0             // Assume number is not prime
        addi  x9, x0, 2              // Smallest prime number

        blt   x10, x9, NotPrime      // Numbers below 2 are not prime

        addi  x7, x0, 2              // First possible divisor


// --------------------------------------------------------
// Try the current divisor.
//
// If divisor equals the candidate, all smaller divisors
// have failed and the candidate is prime.
// --------------------------------------------------------

DivisorLoop:
        beq   x7, x10, PrimeFound

        add   x8, x10, x0            // Remainder = candidate


// --------------------------------------------------------
// Calculate candidate remainder divisor.
//
// Repeatedly subtract the divisor until the remaining
// value is smaller than the divisor.
// --------------------------------------------------------

RemainderLoop:
        blt   x8, x7, NextDivisor

        sub   x8, x8, x7             // Remainder -= divisor

        beq   x8, x0, NotPrime       // Exact division means not prime

        jal   x0, RemainderLoop


// Current divisor did not divide the candidate evenly.

NextDivisor:
        addi  x7, x7, 1              // Try the next divisor
        jal   x0, DivisorLoop


// Candidate is prime.

PrimeFound:
        addi  x12, x0, 1             // Return true
        jalr  x0, 0(x1)


// Candidate is not prime.

NotPrime:
        addi  x12, x0, 0             // Return false
        jalr  x0, 0(x1)


EndProgram:
